package problem60_Permutation_Sequence;

import java.util.LinkedList;
import java.util.List;

public class Solution {
	public String getPermutation(int n, int k) {
		int factorial=1;
		List<Integer> number=new LinkedList<>();
		for(int i=1;i<=n;i++){
			factorial*=i;
			number.add(i);
		}
		if(k>factorial) return "";
		k--;
		StringBuilder sb=new StringBuilder();
		while(n>0){
			factorial/=n;
			sb.append(number.remove(k/factorial));
			k%=factorial;
			n--;
		}
		return sb.toString();
    }
}
